package com.liuzhilong.infrastructure.framework.algorithms.algorithms;

import java.util.List;

/**
 * <h2>反转列表</h2>
 */
public class ReverseLinkedList {
    /**
     * <h2>根据起点终点反转列表</h2>
     * <pre>
     *     反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
     *
     * 说明:
     * 1 ≤ m ≤ n ≤ 链表长度。
     *
     * 示例:
     *
     * 输入: 1->2->3->4->5->NULL, m = 2, n = 4
     * 输出: 1->4->3->2->5->NULL
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
     * </pre>
     * <p>
     *     解法，思想是把要逆转的节点，插入到逆转队列开头。
     *
     *     还有一种做法是利用stack，先进后出的思想。
     *
     * </p>
     * @param head
     * @param left
     * @param right
     * @return
     */
    public ListNode reverseBetween(ListNode head, int left, int right) {

        ListNode rightNode = null;
        ListNode preLeftNode = null;
        ListNode leftNode = null;
        ListNode current = head;
        int index = 0;
        while(++index<=right){
            if(index>=left){
                //
                if(rightNode==null){//第一个交换的
                    rightNode = current;
                    leftNode = current;
                }else {
                    //
                    rightNode.next = current.next;
                    current.next = leftNode;
                    if(preLeftNode!=null){
                        preLeftNode.next = current;
                    }
                    leftNode = current;
                }
                current = rightNode.next;
            }else {
                preLeftNode = current;
                current = current.next;
            }
        }
        return preLeftNode==null?leftNode:head;
    }
}
 class ListNode {
 int val;
  ListNode next;
  ListNode() {}
  ListNode(int val) { this.val = val; }
  ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
